1. Field of the Invention
The present invention relates to systems and methods of communicating information in packet-switched networks, and in particular to a method and system for communicating uplink data packets from an earth station to a satellite while minimizing transport delay.
2. Description of the Related Art
Satellite networks have become a popular means to disseminate information over a wide area Transception of data over satellite networks must comply with certain access protocols that are suitable for the type of data to be transmitted. The access protocol determines how channel bandwidth will be allocated among system users. One such access protocol is the medium access control (MAC) protocol. In the past, the dominant media form transmitted over such networks has been computer data. However, in recent years, there has been a need to provide interactive, real-time multimedia such as medium quality interactive video over such networks. To provide such information, the underlying networks must be capable of delivering communication services complying with a specified Quality of Service (QoS) criteria. At the MAC sub-layer, this QoS amounts to some statistical guarantees on packet delay, delay variance, and loss.
In satellite networks, MAC protocols must be applied to the uplink (earth terminal to satellite) channel. Since the uplink is shared between many users and is hence a shared channel, the MAC protocol can have a significant effect on the QoS the network is capable of delivering. In designing a MAC for bursty variable bit-rate (VBR) sources in a high latency system, there is a tradeoff between uplink utilization and achievable delay. For instance, a MAC protocol technique that delivers a high link utilization (and thus a high network capacity) will almost always produce poor packet delays. This is because the instantaneous bandwidth requirements of each node (earth terminal) must be determined in order to perform an optimal allocation of network resources. This can lead to excessive transmission delays. This is particularly so when used with high latency systems such as satellite networks operating in geosynchronous orbit (GEO). In GEO satellite systems, the distance between the ground station and the satellites itself is a significant source of data latency.
Currently, individuals can purchase a relatively small satellite dish capable of two-way communication with a GEO satellite. These can be used by individual households, companies, universities, and many other xe2x80x9cusersxe2x80x9d who do not have access to a broadband wired infiastructure. This xe2x80x9cpersonal earth terminalxe2x80x9d model raises the specter of many low bit-rate terminals sharing a common uplink channel. Because there are many personal terminals, there are potentially few sources being aggregated at the uplink point. This can lead to source traffic that is highly bursty, which presents problems in efficient MAC protocol design.
There are several methods for gaining channel access in a shared channel system. These methods vary from random access (RA) to fixed bandwidth allocation (FBA) protocols. The QoS that these techniques can deliver varies as well. The simplest form of random access is an access protocol wherein the remote users (in this case, earth terminals) transmit packets in an uncoordinated manner. Since collision-free channel resources cannot be guaranteed with RA methods, QoS guarantees, in terms of packet loss and delay, are very weak. However, such random, uncoordinated transmission protocols do offer reduced control signaling and algorithmic overhead, and in ease of implementation. Random access MAC protocols are traditionally employed when the network traffic is unpredictable and bursty.
With fixed bandwidth allocation (FBA) protocols, medium access is accomplished when the connection is set up. A terminal acquires a fixed amount of channel resources and maintains this resource for the life of the connection. The only time the amount of channel resource may change is when the connection is preempted by another connection with higher priority. FBA protocols are capable of delivering much stronger QoS guarantees than RA protocols. However, this QoS improvement comes at the expense of system capacity. For example, in cases where the source has a varying bit-rate (VBR), simply acquiring channel bandwidth greater than or equal to its peak rate will provide a relatively firm upper bound on the delays of packets entering the network. However, since the source is VBR, uplink channel resources will be wasted when the source is producing packets at a rate less than the peak rate. This poor link utilization leads to low network capacity (i.e. the number of terminals that can be supported within a given amount of uplink bandwidth).
FIG. 1 is a diagram showing the operation of a communication system using a demand assigned multiple access (DAMA) protocol. DAMA techniques, which address the capacity issue by using instantaneous bandwidth demands to statistically multiplex many VBR sources on one channel, can be used to deliver predictable delays without the poor capacity of FBA
DAMA based MAC protocols comprise two primary elements: (1) a bandwidth request mechanism and (2) a mechanism for coordinated transmission. The bandwidth request mechanism normally consists of dedicated bandwidth for each terminal such as earth station 104 residing in a xe2x80x9crequest phase.xe2x80x9d The transmission of data packets occurs in the xe2x80x9cdata phasexe2x80x9d. The separation of these two phases is accomplished by a physical layer (PHY) protocol such as frequency division multiple access (FDMA), time division multiple access (TDMA), or code division multiple access (CDMA). In the request phase, data bandwidth is reserved by the earth station (ES) by a resource request module 116 forming and transmitting a resource requesting having a resource metric that represents the current value of the earth station""s 104 desired bandwidth. This resource request phase allows the ES to communicate their instantaneous bandwidth needs to an allocating agent (AA) 108, which performs bandwidth allocation. In a satellite network 100, the AA 108 resides either at the satellite (denoted 108A) or at a terrestrial master control station (MCS) 106 (denoted 108B). Once the AA 108 has received the bandwidth requests of all terminals and earth stations 104, it decides how much channel resources (or resource units) to allocate to each terminal using an allocation algorithm (AAlg). Each earth station 104 is then informed, via a downlink channel, how many resource units (allocated frequencies in FDMA, time slot in CDMA, and codes in CDMA) it will receive and when to begin transmission. By informing each terminal when to transmit, the AA accomplishes coordinated transmission. This MAC scheme results in a system wherein the time varying bandwidth needs of any terminal can be accommodated. The only time insufficient bandwidth is allocated is when several stations 104 are producing traffic at close to their peak rates. When this occurs, some terminals may not get all of the channel bandwidth they requested. Because of this possibility, the QoS guarantees, in terms of delay bounds, are not as firm as the fixed bandwidth allocation case.
There are two main drawbacks to DAMA techniques, however. They are (1) bandwidth loss due to request signaling (2) and increased packet delay times. In a pure DAMA protocol, each data packet must wait a round trip time (i.e. twice the time required to transmit a packet between the earth station 104 and the allocating agent 108A at the satellite) before it can begin transmission. Due to the high delay (latency) in satellite networks (particularly those in GEO), the process of passing DAMA request information between an earth terminal and the satellite can be very time consuming. For example, for GEO systems, the delay in a transmission from an earth terminal to a satellite (hop delay D) is on the order of 135 milliseconds. If the AA 108 is located at the satellite, the time between a packet""s arrival at the terminal output queue and its actual start of transmission on the uplink channel is lower bounded by 2D. If the AA is located at the terrestrial MCS 106, this time is now lower bounded by 4D. Hence, the link utilization benefits of DAMA bring with it a substantial increase in end-to-end delay, which can substantially reduce performance. Bandwidth is expended in transmitting the DAMA request metric. For instance, in a TDMA system the request metric is traditionally transmitted in a dedicated xe2x80x9cmini-slotxe2x80x9d at each TDMA frame. The frequency of this signaling must be kept high in order to minimize packet delay. This leads to a non-negligible amount of bandwidth that is lost to DAMA control. Hence, there are drawbacks associated with the foregoing pure-DAMA techniques.
These drawbacks are addressed in hybrid DAMA techniques. Hybrid DAMA improves on the delay performance of pure DAMA, without sacrificing the channel utilization benefits. Hybrid DAMA medium access schemes are MAC protocols in which a portion of the bandwidth is allocated in a demand assigned manner.
As described above, packets crossing DAMA systems capable of on-board satellite 102 switching will wait in the output queue of the earth terminal a minimum of 2D. This implies that the time to cross the satellite 102 portion of the end-to-end path is lower bounded by 4D. Therefore this 4D delay is the mark by which hybrids of DAMA must be measured. When considering real-time sources (such as source coded video), this 4D lower bound, (which is approximately 540 milliseconds for GEO satellite systems 100) can prove to be prohibitive in providing suitable QoS.
Suppose source coded VBR video defines a sustained data stream. In such cases, the video source has an average bit rate and the instantaneous bit rate deviates about this average. However, the bit rate never drops to zero. Recognizing this, hybrid DAMA MACs have been proposed.
Let BT represent the total uplink bandwidth and NET be the number of earth terminals with ongoing sustained stream connections. In the hybrid DAMA protocol, each earth station 104 is allocated a fixed number of resource units (i.e., in TDMA, slots) xcfx81fx in every TDMA uplink frame. The bandwidth that remains, Bxe2x88x92NETxc2x7xcfx81fx is made available on a demand assigned basis. In each TDMA frame, control slots are set aside for each earth terminal to transmit its output queue size. Using this information, the AA at the satellite 108A assigns the remaining Bxe2x88x92NETxc2x7xcfx81fx bandwidth. This technique can be thought of as a hybrid fixed bandwidth allocation and demand assigned multiple access or FBA/DAMA. This scheme seeks to exploit the fact that the bit rate of a sustained stream never drops to zero. Under certain loading conditions, this FBA/DAMA technique out performs DAMA and FBA.
However, there are two drawbacks to the FBA/DAMA technique. First, continually measuring and sending the output queue size every TDMA frame requires constant processing at both the satellite 102 and the earth station 104. Transmitting this queue size metric each frame in mini-slots wastes uplink bandwidth. Second, and more importantly, the DAMA part of this technique attempts to track the instantaneous queue size, which changes rapidly.
FIG. 2 is a control system 200 that illustrates the demand assigned multiple access protocol. The difference between the requested resource units 202 (representing the output queue) and the allocated resource units 208 provides an error signal, which becomes the DAMA request 204. The request 204 is delayed by a delay element 206 representing transmission delays before receipt by the allocating agent 108A and delayed again by another delay element 206 before the resource unit allocation 208 is received at the earth station 104. In a satellite network 100 of GEO satellites 102, the loop delay is 2D, which renders the tracking of the instantaneous queue size inaccurate.
There is therefore a need for a medium access control protocol that allows transmission of information with minimal delay, while simultaneously maximizing resource unit utilization. The present invention satisfies that need.
To address the requirements described above, the present invention discloses a method, apparatus, and an article of manufacture for communicating data from a first node to a second node. The method comprises the steps of receiving input data at the first node, transmitting a resource request having a resource metric from the first node to an allocating agent, receiving an allocation of resource units according to the resource metric, the resource units comprising at least one DAMA channel resource metric and at least one RA channel resource unit, queuing the input data into the DAMA channel buffer, dequeuing input data from the DAMA channel buffer into the RA channel buffer according to a comparison between a predicted transmission delay and a delay threshold, and transmitting the dequeued input data in the RA channel buffer via the RA resource units. The article of manufacture comprises a data storage device tangibly embodying instructions to perform the method steps described above.
The apparatus comprises a receiver for receiving input data, a DAMA channel buffer for accepting the input data, a resource unit request module, operatively coupled to the transmitter and the receiver, the resource unit request module for generating a resource request metric when indicated by an information rate of the input data, and for receiving an allocation of resource units via the receiver, and a channel selection module, for dequeuing input data from the DAMA channel buffer to an RA channel buffer according to a predicted channel delay and a delay threshold.
The MAC protocol described herein is of the demand assigned multiple access (DAMA) family. The disclosed protocol uses a DAMA request metric which attempts to measure the slow time behavior of source coded video. This request metric is used with a channel that is both random access (RA) and DAMA, and describes a MAC protocol which solves the delay/capacity trade-off by introducing slight packet loss that can be tolerated by most real-time multimedia applications (voice and video).
For example, the MAC protocol described herein can be advantageously used with video conferencing tools running over an Internet MBone. The Mbone is a virtual network running over the physical Internet, which serves as a testbed for delivering multimedia services to many users via IP multicast. Currently, the Internet provides only best effort delivery of packets which provides no QoS guarantee. This causes current real-time MBone applications to see heavy packet loss under certain congestion conditions. We will define at this point medium quality video to be interactive applications, which produce traffic at average rates less than 500 kb/s and can tolerate packet loss of 5 percent or less. This definition describes most interactive applications currently using the MBone.